這是個問題：充滿熱情懷抱理想，還沒被摧殘過的鐵人賽第一天，到底要快樂的寫寫廢文前言，還是要直接進入正題呢。

雖然想廢一點逃避一下，不過既然最後還是得面對，就乾脆直接開始吧。

這次的主題是研究各種奇奇怪怪的解題技巧，可能存在於演算法課本的某個角落也或許根本沒有，總之有一堆沒寫過根本不會想到的東西。

總之，這系列的內容應該有一部份稍微像演算法，另外也有一部份在講一些特定的、解題需要的資料結構。

今天介紹的是 prefix sum，最基本的概念很簡單，就是把 array 加總儲存，需要的時候再取出用來快速計算。

例如 303. Range Sum Query - Immutable 這個區間加總題，一開始會給定一個 array，然後每次返回特定區間的總和。

所以把陣列遞迴相加，位置 i 儲存 arr[0] 到 arr[i] 的總和，最後用給定相減就可以完成了。

class NumArray:
    def __init__(self, nums: List[int]):
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]
        self.arr = nums
        self.arr.append(0)

    def sumRange(self, left: int, right: int) -> int:
        return self.arr[right] - self.arr[left-1]

304. Range Sum Query 2D - Immutable 也不難，就是空間從一維到二維，要稍微想一下怎麼處理。

這兩題應該算是 prefix sum 入門題，沒有太多變化也不需要其他解題技巧，之後其他的變化題就沒這麼輕鬆了。

Prfix Sum List:

• 303. Range Sum Query - Immutable
• 304. Range Sum Query 2D - Immutable